package com.googlecode.curvedmetromaps.core.model.importer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import com.googlecode.curvedmetromaps.core.model.MetroLine;
import com.googlecode.curvedmetromaps.core.model.MetroMap;
import com.googlecode.curvedmetromaps.core.model.MetroStation;

public abstract class MapParser {
	public abstract void parse(String resource, final MetroMap map);

	/**
	 * Converts a mapping of stations to a MetroLine by finding an Euler trail.
	 * 
	 * @param stations
	 *            Stations stored by reference.
	 * @param edges
	 *            Keys of hashmap are sources and values are a set of targets.
	 */
	protected static MetroLine createMetroLine(
			Map<String, MetroStation> stations,
			HashMap<String, HashSet<String>> edges) {

		// Get an EulerTrail from the set of edges
		EulerTrail eulerTrail = new EulerTrail(edges);
		List<String> stationIds = eulerTrail.getEulerTrail();

		// Map stationIds to MetroStations.
		ArrayList<MetroStation> stationList = new ArrayList<MetroStation>(
				stationIds.size());
		for (String stationId : stationIds) {
			if (stations.containsKey(stationId))
				stationList.add(stations.get(stationId));
			else
				System.out.println("Stop is not a metro station: " + stationId);
		}

		// Convert list of MetroStations to MetroLine.
		MetroLine metroLine = new MetroLine(stationList);

		return metroLine;
	}
	
	protected static ArrayList<MetroLine> removeDuplicateLines(ArrayList<MetroLine> metroLines) {
		ArrayList<MetroLine> results = new ArrayList<MetroLine>();
		
		for (int i = 0; i < metroLines.size(); i++) {
			MetroLine mi = metroLines.get(i);
			
			if (mi.stations.length == 0) continue;

			// Loop through all metro lines after mi and break if a duplicate is found.
			boolean hasDuplicate = false;
			for (int j = i+1; j < metroLines.size(); j++) {
				MetroLine mj = metroLines.get(j);
				// Only lines with the same length have the potential to be a duplicate.
				if (mj.stations.length == mi.stations.length) {
					// Loop through all stations and break if a difference is found.
					boolean isMatch = true;
					for (int k = 0; k < mj.stations.length; k++) {
						if (mj.stations[k] != mi.stations[k] && mj.stations[k] != mi.stations[k]) {
							isMatch = false;
							break;
						}
					}
					if (isMatch) {
						hasDuplicate = true;
						break;
					}
				}
			}

			// Add station to results if it is not a duplicate.
			if (hasDuplicate == false) {
				results.add(mi);
			} else {
				System.out.println("MetroLine " + mi.ref + " will not be added because it is not unique.");
			}
		}
		
		return results;
	}

	/**
	 * Removes nodes that are not stations, leaving the edges between stations.
	 * 
	 * @param stations
	 *            Stations stored by reference.
	 * @param edges
	 *            Keys of hashmap are sources and values are a set of targets.
	 */
	protected static void removeNonStationEdges(
			Map<String, MetroStation> stations,
			HashMap<String, HashSet<String>> edges) {
		// Make graph undirected and remove self-edges.
		makeUndirected(edges);
		
		// Iterate over nodes
		for (Iterator<Entry<String, HashSet<String>>> it = edges.entrySet()
				.iterator(); it.hasNext();) {
			Map.Entry<String, HashSet<String>> kv = it.next();
			String src = kv.getKey();
			// Check if node is not a metrostation
			if (stations.containsKey(src))
				continue;

			HashSet<String> adj = kv.getValue();
			for (String s1 : adj) {
				if (s1.equals(src) == false) {
					// Connect all adjacent nodes with each other.
					for (String s2 : adj) {
						if (s2.equals(src) == false && s1.compareTo(s2) < 0) {
							edges.get(s1).add(s2);
							edges.get(s2).add(s1);
						}
					}
					// Remove connection to src
					edges.get(s1).remove(src);
				}
			}
			// Remove non-station
			it.remove();
		}
	}

	/**
	 * If a station is not connected by edges, it will replace the closest
	 * non-station node.
	 * 
	 * @precondition edges is undirected graph without self-loops.
	 * @param stations
	 *            Stations stored by reference, which are stops in MetroLine
	 *            described by edges.
	 * @param edges
	 *            Keys of hashmap are sources and values are a set of targets.
	 */
	protected static void insertMissingStations(
			Map<String, MetroStation> stations,
			Map<String, MetroStation> nodes,
			HashMap<String, HashSet<String>> edges) {
		// Make graph undirected and remove self-edges.
		makeUndirected(edges);
		
		for (Map.Entry<String, MetroStation> kv : stations.entrySet()) {
			String stationRef = kv.getKey();
			if (edges.containsKey(stationRef) == false) {
				float stationX = kv.getValue().geoX;
				float stationY = kv.getValue().geoY;

				// MetroStation is separate from track, find closest node
				float minDist = Float.POSITIVE_INFINITY;
				String minRef = null;
				for (String nodeRef : edges.keySet()) {
					if (nodes.containsKey(nodeRef)) {
						MetroStation nodeStation = nodes.get(nodeRef);
						float dX = nodeStation.geoX - stationX;
						float dY = nodeStation.geoY - stationY;
						float dist = dX * dX + dY * dY;
						if (dist < minDist) {
							minDist = dist;
							minRef = nodeRef;
						}
					}
				}
				
				// Replace minRef by stationRef in edges.
				replaceStation(minRef, stationRef, edges);
			}
		}
	}

	protected static void mergeStationsWithSameName(
			Map<String, MetroStation> stations,
			HashMap<String, HashMap<String, HashSet<String>>> edgeSets,
			HashMap<String, String> replacedStations) {
		// Copy map into array
		MetroStation[] stationArray = new MetroStation[stations.size()];
		stationArray = stations.values().toArray(stationArray);
		
		HashMap<String, HashSet<String>> stationByLabel = new HashMap<String, HashSet<String>>();
		for (MetroStation m : stations.values()) {
			if (stationByLabel.containsKey(m.label) == false)
				stationByLabel.put(m.label, new HashSet<String>());
			stationByLabel.get(m.label).add(m.ref);
		}
		
		for (Map.Entry<String, HashSet<String>> kv : stationByLabel.entrySet()) {
			if (kv.getValue().size() >= 2) {
				String[] refs = new String[kv.getValue().size()];
				refs = kv.getValue().toArray(refs);
				String targetRef = refs[0];
				for (int i = 1; i < refs.length; i++) {
					String ref = refs[i];
					// Merge ref into targetRef for all edgeSets
					for (HashMap<String, HashSet<String>> edges : edgeSets.values()) {
						if (edges.containsKey(ref)) {
							mergeStations(ref, targetRef, edges);
						}
					}
					// Remove ref as a MetroStation
					replacedStations.put(ref, targetRef);
					stations.remove(ref);
				}
			}
		}
		
		for (HashMap<String, HashSet<String>> edges : edgeSets.values()) {
			// Make graph undirected and remove self-edges introduced by merging stations.
			makeUndirected(edges);
		}
	}

	private static void mergeStations(String oldRef, String newRef, HashMap<String, HashSet<String>> edges) {
		if (oldRef != null && newRef != null) {
			if (edges.containsKey(oldRef)) {
				if (edges.containsKey(newRef) == false)
					edges.put(newRef, new HashSet<String>());

				HashSet<String> oldDst = edges.get(oldRef);
				// Remove all links to oldRef and add them to newRef
				edges.remove(oldRef);
				for (String dst : oldDst) {
					edges.get(newRef).add(dst);
					edges.get(dst).remove(oldRef);
					edges.get(dst).add(newRef);
				}
			}
		}
	}

	private static void replaceStation(String oldRef, String newRef, HashMap<String, HashSet<String>> edges) {
		if (oldRef != null) {
			HashSet<String> destinations = edges.get(oldRef);
			edges.put(newRef, destinations);
			edges.remove(oldRef);
			for (String dst : destinations) {
				edges.get(dst).remove(oldRef);
				edges.get(dst).add(newRef);
			}
		}
	}
	
	private static void makeUndirected(HashMap<String, HashSet<String>> edges) {
		// Make edges undirected. Make a copy of the keySet to avoid concurrent
		// modification.
		HashSet<String> sources = new HashSet<String>(edges.keySet());
		for (String source : sources) {
			for (String target : edges.get(source)) {
				if (target.equals(source) == false) {
					if (edges.containsKey(target) == false)
						edges.put(target, new HashSet<String>());
					edges.get(target).add(source);
				}
			}
			// Remove self-loops
			edges.get(source).remove(source);
		}
	}
	
}
